講義概要/Class Outline

情報科学の基礎として重要なグラフ理論について学ぶ。グラフ構造は様々な場面に出現し、特に情報科学や情報技術を学ぶ場合には、グラフの概念やそれに関わる諸問題や解決法を理解しておくことが重要である。グラフ構造の例としては、例えば、コンピュータネットワークの論理的な構造、カーナビゲーションシステムなどの情報機器で用いられる各種の地図の構造などが代表的なものである。本講義では、グラフの基礎的な概念ならびに各種のグラフの性質、さらにそれらに関わる諸問題について解説する。しっかりとした理解をするためには問題演習が有効であるので、講義形式のみではなく問題演習も適宜行いながら講義を進める。
 

講義計画 /Class Structure

回	内容
1	講義概要 講義概要と計画を説明する。
2	グラフ構造の応用 色々な場面で出現するグラフ構造について、情報科学の観点から紹介する。
3	グラフの表現(集合) 計算機で扱う対象は記号あるいは数値を用いて符号化する必要がある。集合の概念を用いてグラフを符号化する方法について解説する。
4	グラフの表現(行列) 行列の概念を用いてグラフを符号化する方法について扱う。具体的には、隣接行列と接続行列について解説する。
5	次数 次数の概念ならびに関連するグラフの性質について解説する。
6	部分グラフ 部分グラフの概念について解説する。
7	小テスト１ 第６回までの内容についてテストを行う。
8	補足と復習 テストの解説ならびに補足と復習を行う。
9	グラフの同型 ２つのグラフが同型であるという概念について解説する。
10	道と閉路 グラフ中に存在する道と閉路の概念と、関連して距離と直径について解説する。
11	オイラー道 特殊な構造を持つ道である、オイラー道について解説する。
12	木 特殊なグラフ構造である木について解説する。
13	小テスト２ 第８回から第１２回の内容についてテストを行う。
14	補足と復習 テストの解説ならびに補足と復習を行う。